home *** CD-ROM | disk | FTP | other *** search
- From: nak@cbnews.cb.att.com (neil.a.kirby)
- Newsgroups: rec.games.programmer
- Subject: LONG: Intelligent Computer Play -> Paper
- Date: 24 Jul 91 15:08:10 GMT
-
- The following paper was given at the 1991 Computer Game Designers
- Conference.
-
- Copyright 1991 Neil Kirby
- All rights reserved.
-
-
- Intelligent Behavior Without AI:
- An Evolutionary Approach
-
- Copyright 1991 Neil Kirby
-
- Introduction
- This paper describes a way to give intelligent behavior to computer
- operated objects. It traces the evolutionary approach used in the "Auto"
- program of the "Bots" family of games. The Bots system is described to
- provide a context, and the results of each step in the evolution are
- discussed. While the changes made are particular to the Auto program,
- the method is applicable to other programs. The fundamentals of the
- method are:
- 1. Analyze good and bad behaviors.
- 2. Quantify parameters to new algorithms.
- 3. Apply constant evolutionary pressures by repeatedly testing.
- The method has proven to be quite successful. The Auto program has
- progressed from hopelessly poor play to well above average play skills
- without any formal AI methods.
-
- The Basic Approach
- The basic approach greatly resembles classical Darwinistic evolution.
- Start with simplistic behavior, however bad. Simple behavior is best
- described as whatever is easiest to code. Analyze the failures of the
- simple methods. If available, observe the differences between successful
- behavior, especially that of human players, and the failures of the
- computer players. The most difficult step is to identify the parameters
- that can be used to control successful behavior. Once this has been
- done, use regular code to allow the program to react to these parameters.
- The process is completed by repeatedly testing in play. The ease of fast,
- repeated play afforded by computerization accelerates the process. This
- approach is easily observed in the Auto program.
-
- The Bots Family of Games
- The Auto, Aero, and Bots programs make up the Bots family of
- multiplayer, tactical ground and air combat games. These run under the
- Unix System VTM operating system and are written entirely in the C
- programming language. Bots and Auto deal with futuristic ground combat
- units loosely comparable to tanks while Aero deals with flying futuristic
- aircraft. The Bots and Aero programs are used by human players and
- Auto is the computer managed equivalent to Bots. The Bots family of
- games supports but does not require team play.
-
- Since the Bots family are multiple player, multiple process games, events
- are performed simultaneously. A unit can find out the actions of other
- units only after committing its own actions. The events that make up a
- turn are motion, followed by active fire, and ending with passive fire. After
- every ten turns, repair and resupply are made available to a unit. The
- manner in which a unit conducts its motion and fire are strongly
- influenced by the construction of the unit.
-
- Building a Unit
- The units used in Bots and Auto are built according to the tastes of the
- player running them. A unit has six armor facings protecting its internal
- systems from damage. Armor is ablative; each point of damage reduces
- the amount of armor by one. Once a given armor facing is reduced to
- zero, all remaining damage is applied to the internal systems. There are a
- number of internal systems to protect: life support, control, chassis,
- reactor, batteries, hardpoints, weapons, and ammunition. Each has a
- cost and weight associated with it, forcing economic compromises to be
- made to build a unit to meet a given cost. The mobility of a unit is based
- on the amount of power available and the current mass of the unit, both of
- which can change in play.
-
- Weapons
- There are a variety of weapons systems available, each with different
- characteristics. Weapons that require ammunition usually need little
- power while power-based weapons require much more. The lasers are
- relatively light in mass, short-range, and power hungry. Mortars have a
- minimum range and require heavy ammunition, but they also have a long
- maximum range and do not require line of sight to fire. Autocannon inflict
- moderate damage to moderate ranges, but they too, require a large
- amount of moderately heavy ammunition. Miniguns are lighter, smaller,
- short-range versions of the autocannon. Missiles have varying ranges
- and warheads, but they can be shot down by point defenses, and they too,
- are heavy. Particle beam weapons are highly effective in a narrowly
- focused range. Aside from mortars, missiles, and particle beams, most
- weapons improve as range shortens.
-
- The non-offensive weapons systems are stealth, missile defense, and
- hardpoints. Stealth, which is expensive, allows a unit to approach others
- and remain unseen. Missile defense attempts to shoot down incoming
- missiles.
-
- Hardpoints are mounts for optional, single-shot items. The most common
- hardpoint load is a jump pack. Jump packs allow a unit to jump over
- obstacles such as water. They increase the mobility of a unit greatly but
- can only be used once. The other common hardpoint load is an anti-
- aircraft missile.
-
- Play Balance (Rock, Paper, Scissors)
- The selection of a weapon determines much about the unit. Units with
- long-range weapons usually require heavy ammunition. Their great
- weight means limited mobility. Limited mobility implies an inability to
- escape from units with high mobility and short-range weapons. It is
- axiomatic that short-range weapons require high mobility. Therefore,
- short-range weapons must be light to be effective. These trade-offs are
- required for play balance among a wide diversity of systems. Mortar
- units, for example, were popular on teams but few people actually wanted
- to play them.
-
- To be successful in play, a unit must maneuver effectively, fire its
- weapons, and evade enemy fire. It should distribute enemy fire across
- multiple armor facings. If team mates are present, a unit should
- coordinate fire among the team members to combine fire against single
- enemy units. If a unit takes damage, it should flee until it is repaired. The
- richness of detail in the Bots family of games is comparable to that of Star
- Fleet BattlesTM.
-
- Auto units are not allowed to cheat, so the behavior code cannot access
- information that a human player in the same situation would not have. The
- advantage of access to hidden data was considered at first, but has
- proven to be unnecessary. No Auto program was written for Aero units.
- The success of Auto units on the ground removed all demand for an Auto
- equivalent to Aero.
-
- The Original Algorithm
- The original algorithm for Autos was quite simple. The closest enemy unit
- was selected as the target. All other units were ignored. The Auto turned
- to face the enemy and attempted to close. (See Figure 1) After
- maneuvers were complete, the unit attempted to fire its weapons. The fire
- target was the closest enemy within the arc of the weapons fire. The unit
- would not flee if damaged. The unit would not jump unless blocked by
- water, buildings, or steep slopes.
-
- Spreading Out Damage
- There were many failures with the original algorithm. Foremost among
- these was the propensity for the unit to lose its center forward armor and
- take severe internal damage while the left and right forward armor facings
- were pristine. The solution to this problem was for the unit to shorten the
- amount it moved to save sufficient mobility to rotate after its motion. (See
- Figure 2) This rotation would bring the strongest forward armor to face
- the closest enemy unit. Relative bearing and the integer values of the
- forward armor were the parameters that enabled this change, which
- typically tripled the survival of all units. It especially allowed units with
- short-range weapons to close to their effective ranges. This algorithm
- became known as the basic closure code.
-
-
- Self Assessment
- The modified algorithm still had major problems. During a long closure, a
- unit would loose all three forward armor facings, continue closing, and
- take fatal internals. The fix involved self assessment. Before a unit
- started maneuvers, it would evaluate the state of its forward armor,
- internal systems, and ammunition. If all three forward armor facings were
- below minimum, half of any internal system was destroyed, or if
- ammunition was gone, then the unit would declare itself to be unfit for
- battle and flee. It would turn its strongest rear armor toward the closest
- enemy and move as far away as possible. This is just a slightly modified
- version of the basic closure code. If the unit had a jump pack available, it
- would jump as far away as possible. It would choose not to shoot power
- based weapons to save energy for mobility. The parameters for this
- change were simple integer numbers: armor, systems, and ammunition
- counts. This change increased the long term survivability of the Auto
- units greatly. After it, destroying a unit often required a long chase. In
- rolling terrain, enemy units would simply disappear when they were
- seriously damaged.
-
- Battle Range
- At this point, Auto units were interesting but not threatening. Their
- maneuvers were highly predictable. At point blank range a unit would
- close to zero range and stop. Since all motion in Bots is simultaneous,
- human players would simply move forward and turn around, finding
- themselves at near zero range facing the back of the Auto unit. Fatal
- internals for the Auto unit often soon followed. For long-range units such
- as mortars, and specific range units such as particle beam weapons,
- continuos closure was especially counter-productive. Mortar units have a
- minimum range requirement, and care very little about range otherwise.
- In the laser family, where closure improves damage, closure also gives
- the advantage to the lightest and shortest ranged lasers. The fix was to
- establish a battle range (known as BRG) for each weapon type. The
- parameter used with BRG was range.
-
- BRG numbers were tuned during play. While many weapons benefit from
- close range, BRG was picked to balance survivability and the ability to
- inflict damage. Long-range units would prefer to stay at range, denying
- short-range units any fire. If a unit found itself too close, it would back up
- as much as it could. Yet backing up costs twice as much as forward
- motion. BRG helped to keep the long-range support units out of trouble,
- and it helped all units survive combat with a short-range unit. Short-range
- units were still too predictable and easy for human players to destroy.
- BRG was the evolutionary step that set the stage for a major milestone in
- Auto evolution.
-
- The First Major Milestone Change: New Maneuver Code
- The problem with the maneuver code was predictability. The new
- maneuver code dealt with the answers to two questions: "Where can a
- unit go?" and "Where does a unit want to go?" The first question is
- answered by computing the mobility of a unit, which is based on its power
- and mass. The unit can get to roughly any point within a circle, centered
- on the unit, of radius equal to the mobility of the unit. When computing the
- radius of the mobility circle, sufficient mobility is deducted from the radius
- to provide for turns. The second question is answered by BRG. If the
- target does not move, the most effective place to be is some place on a
- circle, centered on the target, of radius BRG. (See Figure 3) If the two
- circles do not intersect, the existing basic closure code is used. If the
- circles intersect, there are three possibilities.
-
- The first possibility is shown in Figure 4. This is the most dangerous case
- for the target, and the best case for the attacker. This situation is most
- often seen when a high mobility unit carrying short ranged weapons
- attacks. The unit will pick a random point on the BRG circle, move to it,
- and turn to face the target. For the target to evade, it must either move far
- enough to get out of range, or it must move behind the random point on the
- BRG circle where the attacker will appear. Neither of these evasions is
- easy. The first requires good mobility, and the second requires good luck.
- If the target does move far enough away to deny weapons fire, the
- attacker will have more power available to move in the next turn.
-
- The second possibility is shown in Figure 5. This is a good case for any
- attacker. This situation is most often seen when a medium or high
- mobility unit carrying medium-range weapons attacks. The unit randomly
- picks one of the two intersection points, moves to it, and turns to face the
- target. Only a target with more mobility than the attacker will be able to
- out maneuver the attacker. As Figure 5 moves toward Figure 4, the
- attacker becomes nearly impossible to evade.
-
- The third case is shown in Figure 6. The mobility circle is inside the BRG
- circle, which means that the attacker is too close. This is usually the
- case when a low mobility unit carrying long-range weapons is closer than
- desired to an enemy unit. Here the unit determines if it would get farther
- away by backing up, or by turning away, moving forward, and turning again
- to face the target. It chooses the way that takes it farthest away and
- executes that maneuver.
-
- BRG and computed mobility, the parameters of the change, are combined
- in an effective algorithm. The effect of the first milestone change was
- dramatic. Attacking units were much more effective (fleeing units were
- unaffected). Human players could no longer destroy Auto units without
- pause. Close combat maneuvers became very dicey. Novice players had
- less than a 50% chance of winning a one-on-one duel. In single combat,
- Auto units played a solid, if uninspired, game and they never made stupid
- errors.
-
- Initial Team Play: Communications
- The team play of Autos still lacked a great deal - they fought as a mob,
- rather than as a team. Any unit that could see no targets would pick a
- random patrol point on the map and head toward it. This scattering
- behavior was good for finding hidden enemy units, but poor for fighting
- enemy teams. If one unit on a team was engaged, the rest of the team
- would ignore the combat unless they too could see the target. Evolution
- continued, as Auto units learned basic communications skills. A unit that
- could see no targets would ask its team for targeting information. The
- other units (Aero, Auto, and Bots) on the same team would reply with the
- map coordinates of the targets that they could see. These coordinates
- could be used the next turn to plot motion. Units that did not require line-
- of-sight to fire, such as mortars, would fire blindly on the map coordinates
- given. The effects of this change were two-fold. It allowed high mobility
- units carrying short-ranged weapons to close upon enemy units that they
- could not see. This meant that once an enemy unit was spotted, all
- unoccupied Autos would head toward it, even in rolling terrain. The
- second effect provided mortar teams with something productive to do.
- Communicating map coordinates proved to be an effective change. To
- the enemy units, it meant to expect mortar fire whenever spotted by any
- member of the Auto team. A particularly nasty combination was to be
- stalked by an unseen stealth unit that was broadcasting coordinates to its
- mortar teammates. This change tended to keep mobs of Autos together,
- but they still fought as a mob.
-
- The Second Major Milestone Change: Improved Team Play
- Targeting was still based on the closest enemy that could be fired at. In
- team play, a lone unit could distract part of a team of Autos and play Pied
- Piper while the rest of the Piper's team destroyed the other part of the
- Auto team. The Piper might not survive, but while it was being destroyed,
- multiple enemy units would be destroyed, tipping the battle against the
- Autos. The second milestone change increased team play. Team play
- was based on the concept of the team target. The enemy unit that
- appeared to be hurt the most would be designated as team target. This
- designation was based on the volume of fire an enemy had absorbed. The
- team target would always be the preferred target for motion control. If the
- team target was between the minimum and maximum effective range for
- the weapons fired, it would be the preferred target for fire as well. The
- results were often devastating and occasionally quite strange. The
- devastating part stemmed from the fact that a single unit, often already
- damaged, could now take all the mortar, long-range missile, autocannon,
- and much of the short-range laser fire that an entire team could inflict.
- The strange part would happen when an Auto unit would move directly
- past and ignore a closer target in order to help destroy the team target.
- But if the team target were not a viable target, each unit would fire as
- before, usually at the closest target.
-
- Mishaps in team play were now fatal. Teams of experts were now doing
- well to achieve a kill ratio of 2.5:1 in favor of the experts. Novice teams
- required two to five times numerical superiority to win. The parameters
- used had been developed in earlier stages of evolution.
-
- Attack Jumps
- Evolution continued as details were refined to solve minor problems. One
- problem was that Autos would only use a jump pack to flee or to cross
- water. This meant that they would often have an unused jump pack at
- reload time, when a new jump pack would be available. The fix was
- simple; units still carrying a jump pack that were near their reload time
- would be free to jump to increase their mobility. The parameter used was
- the unit's turn counter, which already existed. This change made it
- dangerous to rely on predictions about the mobility of an Auto unit. A fast
- moving unit that had been moving four ranges per turn would suddenly
- jump eight and move four more for a total of twelve ranges of motion when
- only four were expected.
-
- Dealing With Aeros
- The final changes involved dealing with Aeros. Bots and Autos usually
- move one to four ranges per turn. Aeros need to move at least ten to
- retain airspeed, and speeds of twenty to fifty are normal. Normal altitudes
- for Aeros typically run from eight to twenty ranges of altitude. The first
- problem Aeros created was that Autos would attempt to set up motion
- based on an Aero target. Since the motion algorithms are optimized for
- non-moving targets, using an Aero to set up motion was ineffective for
- units with a short BRG. It was ineffective for units with a long BRG if the
- Aero was close by, since the bearing of the Aero would change
- dramatically. Even if perfect predictive algorithms were available, only
- units with a long BRG have sufficient range to hurt Aeros at altitude. The
- important changes were range based. All units that had a BRG of 25 or
- higher would prefer any visible enemy Aero to all other targets for fire and
- motion. Units with lower BRG would ignore Aeros when plotting motion,
- but if an Aero was somehow in acceptable range, it would be the preferred
- fire target. At reload time, Autos remembered if they had seen any Aeros
- since last reload and changed their hardpoint weapons mix to prefer anti-
- aircraft missiles. The changes decreased the survivability of Aeros
- greatly. Aero targets were preferred even to team targets, often with the
- same deadly results. The much-maligned mortar units provided greatly
- needed flak fire. Other less popular long BRG units gained a new role.
- Also, the advent of the stealth anti-aircraft missile battery eased the
- problems ground units had with Aeros.
-
- Future Evolution
- There are still several deficiencies with the Auto program. Complex
- terrain tends to mystify Autos, especially urban terrain and bridges. An
- Auto unit will occasionally present weak or down armor toward one enemy
- while fighting another. This single mindedness also shows up when a
- damaged unit flees. Motion directly away from the closest enemy, which
- is always correct in one-on-one, can be fatal when intermixed with an
- enemy team.
-
- Observations About The Process
- Many observations are worth examining. The first of these is that the
- process of analysis and synthesis is regenerative. The initial BRG
- change set the stage for the first milestone change (maneuver code).
- BRG also led to min/max range, which when coupled with
- communications led to the second milestone change (team play). Some
- of the other analysis that went on made it possible and more probable that
- algorithms could be generated to improve poor behavior.
-
- Not as obvious in the paper is the fact that intensive testing helps drive
- the process. The entire evolutionary cycle mentioned above took place at
- lunchtimes over the course of a year. The testing allowed the author to
- observe human behavior in order to model it, and it clearly showed any
- deficiencies in the algorithms.
-
- One very hopeful point is that simple methods often suffice. The long
- closure code and the code for flight is simple but has proven to be very
- effective. The early code, which had numerous deficiencies, was still
- interesting and fun. Between the first and second milestone changes,
- there was, occasionally, the semblance of team behavior by default. If a
- given enemy unit was the best or only target available to a team, the entire
- team fired upon it. In rolling terrain this would be fatal as one unit
- encountered groups of enemy units.
-
- A final point is that the code is well behaved. It is small, runs rapidly, and
- is easy to follow. The behavior control parts of the code do not require
- any extensive calculations. The code is short, with only two files. In fact,
- the Auto program has less source and a smaller executable than the Bots
- program. The increase in size from automation is more than offset by the
- reduction in size gained by deleting the user interface. The control flow of
- the code is relatively easy to follow, and therefore easy to modify.
-
-
- Conclusions:
- The evolutionary method is a viable alternative to exploring AI
- methodologies. The method is universally available to programmers who
- have sufficient time for repeated testing. It is well suited to game
- programs in which the computer and human players deal with the same
- objects and information - - the programmer can model computer behavior
- on successful human behavior. The method fails when the programmer
- cannot identify the keys to changing poor behavior and the default simple
- methods are ineffective. For the multiplayer, tactical combat games that
- this author has written, the methods have produced effective code that is
- fast, compact, and often pleasingly simple.
-
- TM UNIX is a trademark of AT&T Bell Laboratories.
- TM Star Fleet Battles is a trademark of Amarillo Design Burea.
-